from collections import defaultdict


class Solution:
    def maxPointsInsideSquare(self, points: List[List[int]], s: str) -> int:
        """计算每个标签次小距离出现在哪里，正方形不能包含最小次小距离的点
        """
        # 所有标签最小距离的点和距离
        min_d = defaultdict(lambda: inf)
        # 次小距离
        min2 = inf
        
        for (x, y), c in zip(points, s):
            d = max(abs(x), abs(y))
            if d < min_d[c]:
                # d 是目前最小的，那么 min_d[c] 是次小的
                min2 = min(min2, min_d[c])
                min_d[c] = d
            else:
                # d 可能是次小的
                min2 = min(min2, d)
        
        return sum(d < min2 for d in min_d.values())
"""
作者：灵茶山艾府
链接：https://leetcode.cn/problems/maximum-points-inside-the-square/solutions/2775310/er-fen-bian-chang-tong-shi-ji-lu-da-an-z-92w5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
"""

class Solution1:
    def maxPointsInsideSquare(self, points: List[List[int]], s: str) -> int:
        """排序后从内向外搜
        """
        dc = lambda x: max(abs(x[0]), abs(x[1]))
        
        labels = {(x[0],x[1]):c for x, c in zip(points, s)}
        sorted_points = sorted(points, key=dc)
        
        res = set()
        count = 0
        prev_a = 0
        for i, p in enumerate(sorted_points):
            if dc(p) > prev_a:
                prev_a = dc(p)
                count = i
            
            if labels[(p[0], p[1])] in res:
                return count
            else:
                res.add(labels[(p[0], p[1])])
        return len(points)
                
